package chainList;

public class ChainList implements IChainListFunction{
    //定义节点
    /*将节点定义为内部类*/
    static class ChainNode {
        public int value;
        public ChainNode next;
        public ChainNode(int value) {
            this.value = value;
        }
    }

    //头节点标记
    public ChainNode head;

    //头插
    public void addFirst(int value) {
        ChainNode node = new ChainNode(value);
    /*
        if(head==null) {
            head = node;
        } else{
            node.next = this.head;
            this.head = node;
            不论head是否为空，都对头插没有影响
            所以省略如下
        }
    */

        node.next = this.head;
        this.head = node;
    }
    //尾插
    public void addLast(int value) {
        ChainNode node = new ChainNode(value);
        if(this.head==null) {
            this.head = node;
        } else {
            ChainNode cur = this.head;
            while(cur.next!=null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    //指定位置插入
    public void addIndex(int index,int value) throws IndexOutOfBoundsException{
        if(index<0 || index>size()) {
            try {
                throw new IndexOutOfBoundsException("索引越界！");
            } catch(IndexOutOfBoundsException e){
                return;
            }
        }
        ChainNode node = new ChainNode(value);
        if(index==0) {
            node.next = this.head;
            this.head = node;
        } else {
            int i = 1;
            ChainNode cur = this.head;
            while (i != index) {
                cur = cur.next;
                i++;
            }
            node.next = cur.next;
            cur.next = node;
        }
    }
    //删除指定元素的节点
    public void remove(int key) {
        if(this.head==null) {
            System.out.println("空链表，无法执行删除操作！");
        }
        if(this.head.value==key) {
            this.head = this.head.next;
        }
        //先调用findPrev方法，找到待删除节点的前一个节点
        ChainNode prev = findPrev(key);
        if(prev == null) {
            System.out.println("没有你要删除的数据！");
            return;
        } else {
            prev.next = prev.next.next;
        }

    }
    /**
     * 找到待删除节点的前一个节点
     * 找到：返回前一个节点
     * 没找到：返回null
     * 注意：会省略对第一个节点的判断，故在调用前需要先对第一个节点进行判断
     */
    private ChainNode findPrev(int key) {
        ChainNode cur = this.head;
        while(cur.next!=null) {
            if(cur.next.value==key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //输出链表长度
    public int size() {
        ChainNode cur = this.head;
        int count = 0;
        while(cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    //打印链表
    public void disPlay() {
        ChainNode cur = this.head;
        while(cur!=null) {
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //删除链表
    public void clear() {
        while(this.head!=null) {
            //先保存下一个节点
            ChainNode nextNode = this.head.next;
            this.head.value = 0;
            this.head.next = null;
            this.head = nextNode;
        }
    }
}
